Search for: All records

The Minkowski problem for a class of unbounded closed convex sets is considered. This is equivalent to a Monge-Ampère equation on a bounded convex open domain with possibly non-integrable given data. A complete solution (necessary and sufficient condition for existence and uniqueness) in dimension 2 is presented. In higher dimensions, partial results are demonstrated. 

Abstract An affine Pólya-Szegö principle for a family of affine energies, with equality condition characterization, is demonstrated. In particular, this recovers, as special cases, the$$L^p$$ $L^p$affine Pólya-Szegö principles due to Cianchi, Lutwak, Yang and Zhang, and subsequently Haberl, Schuster and Xiao. Various applications of this new Pólya-Szegö principle are shown. 

Abstract Marine N2-fixing cyanobacteria, including the unicellular genus Crocosphaera, are considered keystone species in marine food webs. Crocosphaera are globally distributed and provide new sources of nitrogen and carbon, which fuel oligotrophic microbial communities and upper trophic levels. Despite their ecosystem importance, only one pelagic, oligotrophic, phycoerythrin-rich species, Crocosphaera watsonii, has ever been identified and characterized as widespread. Herein, we present a new species, named Crocosphaera waterburyi, enriched from the North Pacific Ocean. C. waterburyi was found to be phenotypically and genotypically distinct from C. watsonii, active in situ, distributed globally, and preferred warmer temperatures in culture and the ocean. Additionally, C. waterburyi was detectable in 150- and 4000-meter sediment export traps, had a relatively larger biovolume than C. watsonii, and appeared to aggregate in the environment and laboratory culture. Therefore, it represents an additional, previously unknown link between atmospheric CO2 and N2 gas and deep ocean carbon and nitrogen export and sequestration. 

In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer 1 ≤ k ≤ binom(n,2), the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in O(n^{4/3} log² n) time [Katz and Sharir, 1997]. In this paper, we improve their algorithm to O(n^{4/3} log n) time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work [Avraham, Filtser, Kaplan, Katz, and Sharir, 2015] by a factor of roughly log²(m+n) (resp., (m+n)^ε), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future. 

Given a set P of n points in the plane, the unit-disk graph Gr(P) with respect to a parameter r is an undirected graph whose vertex set is P such that an edge connects two points p, q in P if the Euclidean distance between p and q is at most r (the weight of the edge is 1 in the unweighted case and is the distance between p and q in the weighted case). Given a value \lambda>0 and two points s and t of P, we consider the following reverse shortest path problem: computing the smallest r such that the shortest path length between s and t in Gr(P) is at most \lambda. In this paper, we present an algorithm of O(\lfloor \lambda \rfloor \cdot n log n) time and another algorithm of O(n^{5/4} log^{7/4} n) time for the unweighted case, as well as an O(n^{5/4} log^{5/2} n) time algorithm for the weighted case. We also consider the L1 version of the problem where the distance of two points is measured by the L1 metric; we solve the problem in O(n log^3 n) time for both the unweighted and weighted cases.